﻿// 2818. 操作使得分最大.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

/*
https://leetcode.cn/problems/apply-operations-to-maximize-score/description/

给你一个长度为 n 的正整数数组 nums 和一个整数 k 。

一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：

选择一个之前没有选过的 非空 子数组 nums[l, ..., r] 。
从 nums[l, ..., r] 里面选择一个 质数分数 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。
将你的分数乘以 x 。
nums[l, ..., r] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。

一个整数的 质数分数 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 * 2 * 3 * 5 * 5 。

请你返回进行至多 k 次操作后，可以得到的 最大分数 。

由于答案可能很大，请你将结果对 10^9 + 7 取余后返回。



示例 1：

输入：nums = [8,3,9,3,8], k = 2
输出：81
解释：进行以下操作可以得到分数 81 ：
- 选择子数组 nums[2, ..., 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，
分数变为 9 * 9 = 81 。81 是可以得到的最高得分。
示例 2：

输入：nums = [19,12,14,6,10,18], k = 3
输出：4788
解释：进行以下操作可以得到分数 4788 ：
- 选择子数组 nums[0, ..., 0] 。nums[0] 是子数组中唯一的元素。所以我们将分数乘以 nums[0] ，分数变为 1 * 19 = 19 。
- 选择子数组 nums[5, ..., 5] 。nums[5] 是子数组中唯一的元素。所以我们将分数乘以 nums[5] ，分数变为 19 * 18 = 342 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 2，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为  342 * 14 = 4788 。
4788 是可以得到的最高的分。


提示：

1 <= nums.length == n <= 105
1 <= nums[i] <= 105
1 <= k <= min(n * (n + 1) / 2, 10^9)
*/

struct ELE {
    int l; int r; int idx;
    int val;
};

bool cmppp(const struct ELE a, const struct ELE b) {
    return  (a.val < b.val);

}


class Solution {
public:
    vector<int> eleScore;// [100010] ;
    vector<int> leftIdx;// [100010] ;
    vector<int> rightIdx;// [100010] ;
   

    long long quickMi(long long a, int b) {
        long long ret = 1;
        while (b != 0) {
            if (b & 1) {
                ret *= a; ret %= 1000000007;
            }
            a = a *a; a %= 1000000007;
            b >>= 1;
        }

        return ret;
    }

 
    int maximumScore(vector<int>& nums, int k) {
        eleScore.resize(100010,0);
        leftIdx.resize(100010,-1);
        rightIdx.resize(100010, 0x3f3f3f3f);

        for (int i = 0; i < nums.size(); i++) {
            int val = nums[i];
            for (int j = 2; j <= val / j; j++) {
                if(val%j==0) eleScore[i]++;
                while (val % j == 0) {
                    val /= j;
                }
            }
            if (val != 1) eleScore[i]++;
        }
        deque<int> q;
        for (int i = 0; i < nums.size(); i++) {
            while (!q.empty() && eleScore[q.back()] < eleScore[i]) q.pop_back();
            if (!q.empty()) { leftIdx[i] = q.back(); }
            q.push_back(i);
        }

        q.clear();
        for (int i = nums.size() - 1; i >= 0; i--) {
            while (!q.empty() && eleScore[q.back()] <= eleScore[i]) q.pop_back();
            if (!q.empty()) { rightIdx[i] = q.back(); }
            q.push_back(i);
        }
        //===============================================
        int cost = 0;
        long long ans = 1;
        vector<struct ELE> ele(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            ele[i].val = nums[i];
            ele[i].l = leftIdx[i];
            ele[i].r = rightIdx[i];
            ele[i].idx = i;
        }

        sort(ele.begin(), ele.end(), cmppp);

        for (int i = nums.size() - 1; i >= 0; i--) {
            if (ele[i].r == 0x3f3f3f3f)  ele[i].r = nums.size();
            long long currCnt = (ele[i].r - ele[i].idx - 1) * ((ele[i].idx - ele[i].l - 1)) + 
                    ((ele[i].idx - ele[i].l - 1)) + (ele[i].r - ele[i].idx - 1) + 1;
            if (k >= currCnt) {
                ans = ans * quickMi(ele[i].val, currCnt) % 1000000007;
                k -= currCnt;
            }else {
                ans = ans * quickMi(ele[i].val, k) % 1000000007;
                k = 0;
            }
            if (k == 0) break;
        }

        return ans;
    }
};


int main()
{
    Solution s;
    vector<int>  v{ 19,12,14,6,10,18 };
    cout << s.maximumScore(v,3);
}

 